/// @tags: String PGF Probability
#include <cstdio>
#include <iomanip>
#include <iostream>

using namespace std;

namespace BlueQuantum {

int const N = 1e5 + 5, mod = 1e4;

int n, t;
int s[N], nxt[N];

inline int qpow(int base, int exp) {
  int res = 1;
  for (; exp; exp >>= 1, (base *= base) %= mod)
    if (exp & 1) (res *= base) %= mod;
  return res;
}

inline int main() {
  cin >> n >> t;
  for (int i = 1, m; i <= t; ++i) {
    cin >> m;
    for (int j = 1; j <= m; ++j) cin >> s[j];
    int k = nxt[1] = 0;
    for (int j = 2; j <= m; ++j) {
      while (k && s[j] != s[k + 1]) k = nxt[k];
      if (s[j] == s[k + 1]) ++k;
      nxt[j] = k;
    }
    int ans = 0;
    for (int i = m; i; i = nxt[i])
      if ((ans += qpow(n % mod, i)) >= mod) ans -= mod;
    cout << setfill('0') << setw(4) << ans << '\n';
  }
  return 0;
}

}  // namespace BlueQuantum

int main() {
#ifndef ONLINE_JUDGE
#ifdef LOCAL
  freopen("/tmp/CodeTmp/testdata.in", "r", stdin);
  freopen("/tmp/CodeTmp/testdata.out", "w", stdout);
#else
  freopen("P4548 [CTSC2006] 歌唱王国.in", "r", stdin);
  freopen("P4548 [CTSC2006] 歌唱王国.out", "w", stdout);
#endif
#endif

  ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
  return BlueQuantum::main();
}
